﻿//
// (C) Copyright 2009 Irantha Suwandarathna (iranthas@hotmail.com)
// All rights reserved.
//

/* Copyright (c) 2001-2008, The HSQL Development Group
 * All rights reserved.
 *
 * Redistribution and use _in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions _in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer _in the documentation
 * and/or other materials provided with the distribution.
 *
 * Neither the name of the HSQL Development Group nor the names of its
 * contributors may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using EffiProz.Core.Lib;
using EffiProz.Core.DataTypes;
using EffiProz.Core.Indexes;
using EffiProz.Core.Errors;
using EffiProz.Core.Persist;
using EffiProz.Core.Results;
using EffiProz.Core.Navigators;
using EffiProz.Core.Store;

namespace EffiProz.Core
{
    public class RangeVariableResolver
    {
        public RangeVariable[] rangeVariables;
        public Expression conditions;
        public OrderedHashSet rangeVarSet = new OrderedHashSet();
        public ParserDML.CompileContext compileContext;

        //
        public EfzArrayList[] tempJoinExpressions;
        public EfzArrayList[] joinExpressions;
        public EfzArrayList[] whereExpressions;
        public EfzArrayList queryExpressions = new EfzArrayList();

        //
        public Expression[] inExpressions;
        public bool[] flags;

        //
        public OrderedHashSet set = new OrderedHashSet();

        //
        public OrderedIntHashSet colIndexSetEqual = new OrderedIntHashSet();
        public OrderedIntHashSet colIndexSetOther = new OrderedIntHashSet();
        public MultiValueHashMap map = new MultiValueHashMap();
        public int inExpressionCount = 0;
        public bool hasOuterJoin = false;

        public RangeVariableResolver(RangeVariable[] rangeVars, Expression conditions,
                              ParserDML.CompileContext compileContext)
        {

            this.rangeVariables = rangeVars;
            this.conditions = conditions;
            this.compileContext = compileContext;

            for (int i = 0; i < rangeVars.Length; i++)
            {
                RangeVariable range = rangeVars[i];

                rangeVarSet.add(range);

                if (range.isLeftJoin || range.isRightJoin)
                {
                    hasOuterJoin = true;
                }
            }

            inExpressions = new Expression[rangeVars.Length];
            flags = new bool[rangeVars.Length];
            tempJoinExpressions = new EfzArrayList[rangeVars.Length];

            for (int i = 0; i < rangeVars.Length; i++)
            {
                tempJoinExpressions[i] = new EfzArrayList();
            }

            joinExpressions = new EfzArrayList[rangeVars.Length];

            for (int i = 0; i < rangeVars.Length; i++)
            {
                joinExpressions[i] = new EfzArrayList();
            }

            whereExpressions = new EfzArrayList[rangeVars.Length];

            for (int i = 0; i < rangeVars.Length; i++)
            {
                whereExpressions[i] = new EfzArrayList();
            }
        }

        public void processConditions()
        {

            decomposeCondition(conditions, queryExpressions);

            for (int i = 0; i < rangeVariables.Length; i++)
            {
                if (rangeVariables[i].nonIndexJoinCondition == null)
                {
                    continue;
                }

                decomposeCondition(rangeVariables[i].nonIndexJoinCondition,
                                   tempJoinExpressions[i]);

                rangeVariables[i].nonIndexJoinCondition = null;
            }

            conditions = null;

            assignToLists();
            expandConditions();
            assignToRangeVariables();
            processFullJoins();
        }

        /**
         * Divides AND conditions and assigns
         */
        public static Expression decomposeCondition(Expression e,
                                             EfzArrayList conditions)
        {

            if (e == null)
            {
                return Expression.EXPR_TRUE;
            }

            Expression arg1 = e.getLeftNode();
            Expression arg2 = e.getRightNode();
            int type = e.getType();

            if (type == OpTypes.AND)
            {
                arg1 = decomposeCondition(arg1, conditions);
                arg2 = decomposeCondition(arg2, conditions);

                if (arg1 == Expression.EXPR_TRUE)
                {
                    return arg2;
                }

                if (arg2 == Expression.EXPR_TRUE)
                {
                    return arg1;
                }

                e.setLeftNode(arg1);
                e.setRightNode(arg2);

                return e;
            }
            else if (type == OpTypes.EQUAL)
            {
                if (arg1.getType() == OpTypes.ROW
                        && arg2.getType() == OpTypes.ROW)
                {
                    for (int i = 0; i < arg1.nodes.Length; i++)
                    {
                        Expression part = new ExpressionLogical(arg1.nodes[i],
                            arg2.nodes[i]);

                        part.resolveTypes(null, null);
                        conditions.add(part);
                    }

                    return Expression.EXPR_TRUE;
                }
            }

            if (e != Expression.EXPR_TRUE)
            {
                conditions.add(e);
            }

            return Expression.EXPR_TRUE;
        }

        /**
         * Assigns the conditions to separate lists
         */
        public void assignToLists()
        {

            int lastOuterIndex = -1;
            int lastRightIndex = -1;
            for (int i = 0; i < rangeVariables.Length; i++)
            {
                if (rangeVariables[i].isLeftJoin)
                {
                    lastOuterIndex = i;
                }
                if (rangeVariables[i].isRightJoin)
                {
                    lastOuterIndex = i;
                    lastRightIndex = i;
                }

                if (lastOuterIndex == i)
                {
                    joinExpressions[i].addAll(tempJoinExpressions[i]);
                }
                else
                {
                    for (int j = 0; j < tempJoinExpressions[i].size(); j++)
                    {
                        assignToJoinLists(
                            (Expression)tempJoinExpressions[i].get(j),
                            joinExpressions, lastOuterIndex + 1);
                    }
                }
            }

            for (int i = 0; i < queryExpressions.size(); i++)
            {
                assignToWhereLists((Expression)queryExpressions.get(i),
                                   whereExpressions, lastRightIndex);
            }
        }

        /**
         * Assigns a single condition to the relevant list of conditions
         *
         * Parameter first indicates the first range variable to which condition
         * can be assigned
         */
        public void assignToJoinLists(Expression e, EfzArrayList[] expressionLists,
                               int first)
        {

            set.clear();
            e.collectRangeVariables(rangeVariables, set);

            int index = rangeVarSet.getLargestIndex(set);

            // condition is independent of tables if no range variable is found
            if (index == -1)
            {
                index = 0;
            }

            if (set.size() == 1)
            {
                switch (e.getType())
                {

                    case OpTypes.COLUMN:
                    case OpTypes.EQUAL:
                        break;
                }
            }

            // condition is assigned to first non-outer range variable
            if (index < first)
            {
                index = first;
            }

            expressionLists[index].add(e);
        }

        /**
         * Assigns a single condition to the relevant list of conditions
         *
         * Parameter first indicates the first range variable to which condition
         * can be assigned
         */
        public void assignToWhereLists(Expression e, EfzArrayList[] expressionLists,
                                int first)
        {

            set.clear();
            e.collectRangeVariables(rangeVariables, set);

            int index = rangeVarSet.getLargestIndex(set);

            // condition is independent of tables if no range variable is found
            if (index == -1)
            {
                index = 0;
            }

            // condition is assigned to first non-outer range variable
            if (index < first)
            {
                index = first;
            }

            expressionLists[index].add(e);
        }

        public void expandConditions()
        {
            expandConditions(whereExpressions, false);
            expandConditions(joinExpressions, false);
        }

        public void expandConditions(EfzArrayList[] array, bool isJoin)
        {

            for (int i = 0; i < rangeVariables.Length; i++)
            {
                EfzArrayList list = array[i];

                map.clear();
                set.clear();

                bool hasChain = false;

                for (int j = 0; j < list.size(); j++)
                {
                    Expression e = (Expression)list.get(j);

                    if (!e.isColumnEqual
                            || e.getLeftNode().getRangeVariable()
                               == e.getRightNode().getRangeVariable())
                    {
                        continue;
                    }

                    if (e.getLeftNode().getRangeVariable() == rangeVariables[i])
                    {
                        map.put(e.getLeftNode().getColumn(), e.getRightNode());

                        if (!set.add(e.getLeftNode().getColumn()))
                        {
                            hasChain = true;
                        }
                    }
                    else
                    {
                        map.put(e.getRightNode().getColumn(), e.getLeftNode());

                        if (!set.add(e.getRightNode().getColumn()))
                        {
                            hasChain = true;
                        }
                    }
                }

                if (hasChain && !(hasOuterJoin && isJoin))
                {
                    Iterator keyIt = map.keySet().iterator();

                    while (keyIt.hasNext())
                    {
                        Object key = keyIt.next();
                        Iterator it = map.get(key);

                        set.clear();

                        while (it.hasNext())
                        {
                            set.add(it.next());
                        }

                        while (set.size() > 1)
                        {
                            Expression e1 = (Expression)set.remove(set.size()
                                - 1);

                            for (int j = 0; j < set.size(); j++)
                            {
                                Expression e2 = (Expression)set.get(j);

                                closeJoinChain(array, e1, e2);
                            }
                        }
                    }
                }
            }
        }

        public void closeJoinChain(EfzArrayList[] array, Expression e1, Expression e2)
        {

            int idx1 = rangeVarSet.getIndex(e1.getRangeVariable());
            int idx2 = rangeVarSet.getIndex(e2.getRangeVariable());
            int index = idx1 > idx2 ? idx1
                                    : idx2;

            array[index].add(new ExpressionLogical(e1, e2));
        }

        /**
         * Assigns conditions to range variables and converts suitable IN conditions
         * to table lookup.
         */
        public void assignToRangeVariables()
        {

            for (int i = 0; i < rangeVariables.Length; i++)
            {
                bool isOuter = rangeVariables[i].isLeftJoin
                                  || rangeVariables[i].isRightJoin;

                if (isOuter)
                {
                    assignToRangeVariable(rangeVariables[i], i,
                                          joinExpressions[i], true);
                    assignToRangeVariable(rangeVariables[i], i,
                                          whereExpressions[i], false);
                }
                else
                {
                    joinExpressions[i].addAll(whereExpressions[i]);
                    assignToRangeVariable(rangeVariables[i], i,
                                          joinExpressions[i], true);
                }

                if (rangeVariables[i].hasIndexCondition()
                        && inExpressions[i] != null)
                {
                    if (!flags[i] && isOuter)
                    {
                        rangeVariables[i].addWhereCondition(inExpressions[i]);
                    }
                    else
                    {
                        rangeVariables[i].addJoinCondition(inExpressions[i]);
                    }

                    inExpressions[i] = null;

                    inExpressionCount--;
                }
            }

            if (inExpressionCount != 0)
            {
                setInConditionsAsTables();
            }
        }

        /**
         * Assigns a set of conditions to a range variable.
         */
        public void assignToRangeVariable(RangeVariable rangeVar, int rangeVarIndex,
                                   EfzArrayList exprList, bool isJoin)
        {

            if (exprList.isEmpty())
            {
                return;
            }

            colIndexSetEqual.clear();
            colIndexSetOther.clear();

            for (int j = 0, size = exprList.size(); j < size; j++)
            {
                Expression e = (Expression)exprList.get(j);

                if (rangeVar.hasIndexCondition())
                {
                    rangeVar.addCondition(e, isJoin);
                    exprList.set(j, null);

                    continue;
                }

                if (e.getIndexableExpression(rangeVar) == null)
                {
                    rangeVar.addCondition(e, isJoin);
                    exprList.set(j, null);

                    continue;
                }

                // can use index
                int type = e.getType();

                switch (type)
                {

                    default:
                        {
                            int colIndex = e.getLeftNode().getColumnIndex();

                            colIndexSetOther.add(colIndex);

                            break;
                        }
                    case OpTypes.EQUAL:
                        if (e.exprSubType == OpTypes.ANY_QUANTIFIED)
                        {
                            Index index = rangeVar.rangeTable.getIndexForColumn(
                                e.getLeftNode().nodes[0].getColumnIndex());

                            // code to disable IN optimisation
                            //                        index = null;
                            if (index != null
                                    && inExpressions[rangeVarIndex] == null)
                            {
                                inExpressions[rangeVarIndex] = e;

                                inExpressionCount++;
                            }
                            else
                            {
                                rangeVar.addCondition(e, isJoin);
                            }

                            exprList.set(j, null);

                            continue;
                        }
                        goto case OpTypes.IS_NULL;
                    // fall through
                    case OpTypes.IS_NULL:
                        {
                            int colIndex = e.getLeftNode().getColumnIndex();

                            colIndexSetEqual.add(colIndex);

                            break;
                        }
                    case OpTypes.NOT:
                        {
                            int colIndex =
                                e.getLeftNode().getLeftNode().getColumnIndex();

                            colIndexSetOther.add(colIndex);

                            break;
                        }
                }
            }

            bool isEqual = true;
            Index idx = rangeVar.rangeTable.getIndexForColumns(colIndexSetEqual);

            if (idx == null)
            {
                isEqual = false;
                idx = rangeVar.rangeTable.getIndexForColumns(colIndexSetOther);
            }

            // different procedure for subquery tables
            if (idx == null && rangeVar.rangeTable.isSessionBased)
            {
                if (!colIndexSetEqual.isEmpty())
                {
                    int[] cols = colIndexSetEqual.toArray();

                    idx = rangeVar.rangeTable.getIndexForColumns(cols);
                }

                if (idx == null && !colIndexSetOther.isEmpty())
                {
                    int[] cols = colIndexSetOther.toArray();

                    idx = rangeVar.rangeTable.getIndexForColumns(cols);
                }
            }

            // no index found
            if (idx == null)
            {
                for (int j = 0, size = exprList.size(); j < size; j++)
                {
                    Expression e = (Expression)exprList.get(j);

                    if (e != null)
                    {
                        rangeVar.addCondition(e, isJoin);
                    }
                }

                return;
            }

            // index found
            int[] cols1 = idx.getColumns();
            int colCount = cols1.Length;

            if (isEqual && colCount > 1)
            {
                Expression[] firstRowExpressions = new Expression[cols1.Length];

                for (int j = 0; j < exprList.size(); j++)
                {
                    Expression e = (Expression)exprList.get(j);

                    if (e == null)
                    {
                        continue;
                    }

                    int type = e.getType();

                    if (type == OpTypes.EQUAL)
                    {
                        int offset =
                            ArrayUtil.find(cols1, e.getLeftNode().getColumnIndex());

                        if (offset != -1 && firstRowExpressions[offset] == null)
                        {
                            firstRowExpressions[offset] = e;

                            exprList.set(j, null);

                            continue;
                        }
                    }

                    // not used in index lookup
                    rangeVar.addCondition(e, isJoin);
                    exprList.set(j, null);
                }

                bool hasNull = false;

                for (int i = 0; i < firstRowExpressions.Length; i++)
                {
                    Expression e = firstRowExpressions[i];

                    if (e == null)
                    {
                        if (colCount == cols1.Length)
                        {
                            colCount = i;
                        }

                        hasNull = true;

                        continue;
                    }

                    if (hasNull)
                    {
                        rangeVar.addCondition(e, isJoin);

                        firstRowExpressions[i] = null;
                    }
                }

                rangeVar.addIndexCondition(firstRowExpressions, idx, colCount,
                                           isJoin);

                return;
            }

            for (int j = 0; j < exprList.size(); j++)
            {
                Expression e = (Expression)exprList.get(j);

                if (e == null)
                {
                    continue;
                }

                if (rangeVar.hasIndexCondition())
                {
                    rangeVar.addCondition(e, isJoin);
                    exprList.set(j, null);

                    continue;
                }

                bool isIndexed = false;

                if (e.getType() == OpTypes.NOT
                        && cols1[0]
                           == e.getLeftNode().getLeftNode().getColumnIndex())
                {
                    isIndexed = true;
                }

                if (cols1[0] == e.getLeftNode().getColumnIndex())
                {
                    if (e.getRightNode() != null
                            && !e.getRightNode().isCorrelated())
                    {
                        isIndexed = true;
                    }

                    if (e.getType() == OpTypes.IS_NULL)
                    {
                        isIndexed = true;
                    }
                }

                if (isIndexed)
                {
                    rangeVar.addIndexCondition(e, idx, isJoin);
                }
                else
                {
                    rangeVar.addCondition(e, isJoin);
                }

                exprList.set(j, null);
            }
        }

        /**
         * Converts an IN conditions into a JOIN
         */
        void setInConditionsAsTables()
        {

            for (int i = rangeVariables.Length - 1; i >= 0; i--)
            {
                RangeVariable rangeVar = rangeVariables[i];
                Expression ine = inExpressions[i];

                if (ine != null)
                {
                    Index index = rangeVar.rangeTable.getIndexForColumn(
                        ine.getLeftNode().nodes[0].getColumnIndex());
                    RangeVariable newRangeVar =
                        new RangeVariable(ine.getRightNode().subQuery.getTable(),
                                          null, null, null, compileContext);
                    RangeVariable[] newList =
                        new RangeVariable[rangeVariables.Length + 1];

                    ArrayUtil.copyAdjustArray(rangeVariables, newList,
                                              newRangeVar, i, 1);

                    rangeVariables = newList;

                    // make two columns as arg
                    ColumnSchema left = rangeVar.rangeTable.getColumn(
                        ine.getLeftNode().nodes[0].getColumnIndex());
                    ColumnSchema right = newRangeVar.rangeTable.getColumn(0);
                    Expression e = new ExpressionLogical(rangeVar, left,
                                                         newRangeVar, right);

                    rangeVar.addIndexCondition(e, index, flags[i]);

                    rangeVar.addCondition(ine, true);
                }
            }
        }

        void processFullJoins()
        {

            for (int i = 0; i < rangeVariables.Length; i++)
            {
                if (rangeVariables[i].isRightJoin) { }
            }
        }
    }
}
